//Given an array of integers citations where citations[i] is the number of citat
//ions a researcher received for their ith paper, return compute the researcher's 
//h-index. 
//
// According to the definition of h-index on Wikipedia: A scientist has an index
// h if h of their n papers have at least h citations each, and the other n − h pa
//pers have no more than h citations each. 
//
// If there are several possible values for h, the maximum one is taken as the h
//-index. 
//
// 
// Example 1: 
//
// 
//Input: citations = [3,0,6,1,5]
//Output: 3
//Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each o
//f them had received 3, 0, 6, 1, 5 citations respectively.
//Since the researcher has 3 papers with at least 3 citations each and the remai
//ning two with no more than 3 citations each, their h-index is 3.
// 
//
// Example 2: 
//
// 
//Input: citations = [1,3,1]
//Output: 1
// 
//
// 
// Constraints: 
//
// 
// n == citations.length 
// 1 <= n <= 5000 
// 0 <= citations[i] <= 1000 
// 
// Related Topics 数组 计数排序 排序 
// 👍 223 👎 0


package leetcode.editor.cn;

import java.util.Arrays;

//Java：H-Index
class P274HIndex {
    public static void main(String[] args) {
        Solution solution = new P274HIndex().new Solution();
        solution.hIndex(new int[]{0, 1, 3, 5, 6});
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int hIndexSort(int[] citations) {
            Arrays.sort(citations);
            int h = 0, i = citations.length - 1;
            while (i >= 0 && citations[i] > h) {
                h++;
                i--;
            }
            return h;
        }

        public int hIndex(int[] citations) {
            int n = citations.length, tot = 0;
            int[] counter = new int[n + 1];
            for (int i = 0; i < n; i++) {
                if (citations[i] >= n) {
                    counter[n]++;
                } else {
                    counter[citations[i]]++;
                }
            }
            for (int i = n; i >= 0; i--) {
                tot += counter[i];
                if (tot >= i) {
                    return i;
                }
            }
            return 0;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}